iT邦幫忙

0

Leetcode: 278. First Bad Version

  • 分享至 

  • xImage
  •  

思路

呼叫API的次數越少越好,因為不確定錯誤會是在前面一點的版本出現,還是後面一點的版本出現,因此最好從中間的版本切入,如果該版本回傳結果為有錯誤的版本,則繼續往前追溯;反之若回傳為正確版本,則繼續往後追溯,直到尋找的版本號邊界交錯。

是Binary search的應用題。

 
 
 

程式

class Solution {
public:
    int firstBadVersion(int n) {
        int bversion = -1;
        int lb = 0, ub = n;
        while( ub >= lb ) {
            int index = lb + (ub - lb) / 2;
            if ( isBadVersion(index) ) {
                ub = index - 1;
                bversion = index;
            }
            else
                lb = index + 1;
        }
        return bversion;
    }
};

 
 

打鐵趁熱的話

了解題目到寫完程式,我花了10分鐘,還是可以再更快一點> 口 <。


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言